Lambda the Ultimate

Omniscient debugging is old hat by now, but some of you might still enjoy this video of Bil Lewis talking about the subject. It includes snakes and things, believe it or not...

The first in a planned series of articles that introduces PowerPC ASM.
Assembly language for Power Architecture, Part 1: Programming concepts and beginning PowerPC instructions

Starting with this introduction to assembly language concepts and the PowerPC instruction set, this series of articles introduces assembly language in general and specifically assembly language programming for the POWER5.

It could just be me, but I think the ASM designers could've afforded to make this stuff a bit more human consummable - the preference is on the side of terseness:

li 0, 1
mr 3, 6
ld 6, 0(4)

Could be expressed a little cleaner as:

load R0, #1
load R3, R6
load R6, #0(R4)

No need for seperate instruction names for operations that are only different in how they load the data. And a clearer delineation of what is a register and what is a constant value. But then my bias for MCC68k is probably showing through. And the extra character for registers probably just makes higher level PL compiled code larger. (Oh well, easy enough to write a pretty viewer if one is so inclined.)

As spotted over on Haskell-cafe, Google Code Search is now available! Of course, someone immediately noticed that Haskell was not yet supported (see the drop down list on the advanced search page), so they asked. If your favourite language is missing (Ehud will be pleased, Ada is already there), ask!

Interestingly, Lua is already there. And I have never heard of Limbo before?

Abdulaziz Ghuloum (Indiana University), An Incremental Approach to Compiler Construction

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, “better write an interpreter instead.”

The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter.

This paper from the Scheme workshop presents an extended tutorial showing how to implement a compiler from Scheme to x86 assembly language. The compiler is written in Scheme, obviously (something that may confuse students, I might add, so beware).

An important aspect of the presentation of the material is that the compiler is built incrementally, and the product of each step is a working compiler for a growing subset of the language. This is similar to the EOPL approach. In contrast many compiler textbooks and courses follow a different route, in which each phase is dedicated to building a different part of the compiler (i.e., lexer, parser etc.), and thus the student only sees how the parts interconnect, and gets the satisfaction of seeing the compiler work, at the very end of the process.

Supporting material can be found here.

Tim Bray writes about advanced IDE feature support for dynamic languages, a subject that was debated here at length a few times.

Lest this turn into the usual flamefest, I suggest concentrating this time on practical implementation approaches that can help with implementing dynamic language support in IDEs.

By Chris Heunen and Bart Jacobs

At first, these Arrows may look somewhat arbitrary. Here we show that they are categorically fairly civilised, by showing that they correspond to monoids in suitable subcategories of bifunctors C^op × C → C. This shows that, at a suitable level of abstraction, arrows are like monads …

It has been awhile since I saw anything new from many of the oldtime LtU editors, and I am beginning to feel worried...

As you may know this is the beginning of the Jewish year (Shana tova to y'all!), so now is a good time to begin posting with renewed strength...

I know this is slightly off topic for LtU, but I see Philip Wadler is collecting material aimed at introducing students and the general public to the discipline of computation, a subject near and dear to my heart.

I will not elaborate my thoughts on this subject here, but I remind people interested in this topic to search the LtU archive (specifically the teaching and learning department) since items related to this goal have appeared here occasionally.

This is also a chance to mention again my suggestion that someone translate Doug Hofstadter's Scientific American columns introducing Scheme to a general audience into Haskell.

From ICFP '06, the 1st informal Workshop on Mechanizing Metatheory comes Nick Benton's "Machine Obstructed Proof: How many months can it take to verify 30 assembly instructions?". It is a one page paper, but seems deserving of some notice.

Nick Benton offers a critique of Coq from the standpoint of an inexperienced user, although I am not sure I would really categorize Benton as "inexperienced". Some interesting quotes:

• "...I have rarely felt as stupid and frustrated as I did during my first few weeks using Coq."
• "Tactical theorem proving is like an extreme form of aspect-oriented programming. This is not A Good Thing...."
• "Just having intermediate stages of the work in a computerized form...proved a major benefit."
• "Automated proving is not just a slightly more fussy version of paper proving and neither...is it really like programming."
• "...but the payoff really came the second time I used Coq: I was able to prove some elementary but delicate results...in just a day or so."

[On edit: moved to a story from a forum post. Sorry. - TM]

I haven't seen any posts about this yet, so I thought I'd point it out: ICFP 06 is over, and there are lots of interesting articles.

E.g. from the Scheme Workshop:

• HOAS: [Barzilay] using higher-order syntax for normal code (not just macros)
• "From Variadic Functions to Variadic Relations: A miniKanren Perspective": [Byrd, Friedman]:
  discusses pseudo-variadic functions
• Termite Scheme [Germain, Feeley, Monnier]: Erlang-style processes in Scheme (the latest version)
• Incremental compiler construction [Ghuloum]
• "SHard: a Scheme to Hardware Compiler" [Saint-Mleux, Feeley, David]: compiling Scheme to FPGAs
• and more..